#include "BSP_Scene.h"
#include "Basic/Stream.h"
#include "Global.h"
#include "BBox.h"

namespace FinalRendering
{
	namespace Engine
	{
		class DamagedEntityException
		{};

		const int BSP_FileVersion = 100;

		Surface::Surface()
		{
			VertexCount = MatID = 0;
			Vertices = 0; CubemapID = -1;
		}

		Surface::~Surface()
		{
			if (Vertices)
				delete [] Vertices;
		}

		BSP_Node::BSP_Node()
		{
			memset(this, 0, sizeof(BSP_Node));
			ChildBits = 0xFFFFFFFF;
			Parent = 0xFFFF;
		}

		void BSP_Node::Destroy()
		{
			if (IsLeaf())
			{
				if (Surfaces)
					delete [] Surfaces;
				if (LeafInfo)
					delete LeafInfo;
			}
			
		}

		bool BSP_Node::HasParent()
		{
			return Parent != 0xFFFF;
		}

		bool BSP_Node::IsLeaf()
		{
			return (ChildBits == 0xFFFFFFFF);
		}

		void LeafInfo::SaveToStream(Stream * s)
		{
			int c = BoundingHull.Faces.Count();
			s->WriteBuffer(&c, 1);
			for (int i=0; i<BoundingHull.Faces.Count(); i++)
			{
				s->WriteBuffer(&BoundingHull.Faces[i]->plane,1);
				c = BoundingHull.Faces[i]->vertices.Count();
				s->WriteBuffer(&c, 1);
				s->WriteBuffer(BoundingHull.Faces[i]->vertices.Buffer(), BoundingHull.Faces[i]->vertices.Count());
				c = Portals.Count();
				s->WriteBuffer(&c, 1);
				s->WriteBuffer(Portals.Buffer(), c);
			}
		}

		void LeafInfo::LoadFromStream(Stream * s)
		{
			int faces = 0;
			s->ReadBuffer(&faces, 1);
			for (int i=0; i<faces; i++)
			{
				ConvexHull::Polygon * p = new ConvexHull::Polygon();
				s->ReadBuffer(&p->plane,1);
				int vcount = 0;
				s->ReadBuffer(&vcount, 1);
				p->vertices.SetSize(vcount);
				s->ReadBuffer(p->vertices.Buffer(), p->vertices.Count());
				BoundingHull.Faces.Add(p);
				s->ReadBuffer(&vcount, 1);
				Portals.SetSize(vcount);
				s->ReadBuffer(Portals.Buffer(), vcount);
			}
		}

		int TraverseBSP(Scene * scene, int node, vec3 & p)
		{
			if (!scene->BSP[node].IsLeaf())
			{
				Plane plane;
				memcpy(&plane, scene->BSP[node].DividePlane, sizeof(float)*4);
				int nxt;
				if (plane.PointDistance(p) >= 0.0)
					nxt = scene->BSP[node].Children[0];
				else
					nxt = scene->BSP[node].Children[1];
				if (nxt != 0xFFFF)
					return TraverseBSP(scene, nxt, p);
				else
					return -1;
			}
			else
				return node;
		}

		void Scene::GetOccupiedBspNode(Volume & v, Array<int> & nodes)
		{
			if (v.Type == Volume::Point)
			{
				int leafID = -1;
				SelectLeaf(v.Position, leafID);
				nodes.Add(leafID);
			}
			else if (v.Type == Volume::Rectangle)
			{
				SelectLeaf(BBox(v.Position-v.Size*0.5f, v.Position+v.Size*0.5f), nodes);
			}
			else if (v.Type == Volume::Sphere)
			{
				SelectLeaf(v.Position, v.Radius, nodes);
			}
			else
				throw gxArgumentException();
		}

		void Scene::ClassifyEntities()
		{
			for (int i=0; i<BSP.Count(); i++)
				if (BSP[i].IsLeaf())
					BSP[i].LeafInfo->Entities.Clear();
			Array<int> nodes;
			for (int i=0; i<Entities.Count(); i++)
			{
				nodes.Clear();
				Volume v;
				IBspEntity * bspEnt = dynamic_cast<IBspEntity *>(Entities[i]);
				if (bspEnt)
				{
					bspEnt->GetVolume(&v);
					
					GetOccupiedBspNode(v, nodes);
					if (nodes[0] != -1)
					{
						BSP[nodes[0]].LeafInfo->Entities.Add(bspEnt);
					}
				}
			}
		}

		struct SceneHeader
		{
			char Identifier[8];
			int Version;
			int VertexCount, BSP_NodeCount, MaterialCount, LightmapCount, PortalCount, PVS_Size;
			int EntityCount;
			char Reserved[128];
			SceneHeader()
			{
				Identifier[0] = 'G';
				Identifier[1] = 'X';
				Identifier[2] = 'F';
				Identifier[3] = 'R';
				Identifier[4] = ' ';
				Identifier[5] = 'B';
				Identifier[6] = 'S';
				Identifier[7] = 'P';
				Version = BSP_FileVersion;
				memset(Reserved, 0, 128);
			}
			bool Verify()
			{
				char idstr[9];
				memcpy(idstr, Identifier, 8);
				idstr[8] = 0;
				if (strcmp(idstr, "GXFR BSP") != 0)
					return false;
				if (Version > BSP_FileVersion)
					return false;
				return true;
			}
		};

		void Scene::Save(const String & fileName)
		{
			FileStream f(fileName, gxfmWrite);
			SceneHeader h;
			h.BSP_NodeCount = BSP.Count();
			h.LightmapCount = Lightmaps.Count();
			h.MaterialCount = MatNames.Count();
			h.VertexCount = Vertices.Count();
			h.PortalCount = Portals.Count();
			h.EntityCount = Entities.Count();
			if (PVS)
				h.PVS_Size = PVS->GetSize();
			else
				h.PVS_Size = 0;
			f.WriteBuffer(&h, 1);
			f.WriteBuffer(Vertices.Buffer(), Vertices.Count());
			f.WriteBuffer(Lightmaps.Buffer(), Lightmaps.Count());
			for (int i=0; i<MatNames.Count(); i++)
				MatNames[i].SaveToStream(&f);
			
			for (int i=0; i<Portals.Count(); i++)
			{
				f.WriteBuffer(&(Portals[i].Leaf1),2);
				f.WriteBuffer(&Portals[i].Polygon->plane, 1);
				int vc = Portals[i].Polygon->vertices.Count();
				f.WriteBuffer(&vc, 1);
				f.WriteBuffer(Portals[i].Polygon->vertices.Buffer(), vc);
			}
			for (int i=0; i<BSP.Count(); i++)
			{
				f.WriteBuffer(&BSP[i].ChildBits,1);
				if (!BSP[i].IsLeaf())
				{
					f.WriteBuffer(BSP[i].DividePlane,4);
				}
				else
				{
					f.WriteBuffer(&BSP[i].PVS_ID, 1);
					f.WriteBuffer(&BSP[i].SurfaceCount, 1);
					for (int j=0; j<BSP[i].SurfaceCount; j++)
					{
						Surface *s = &BSP[i].Surfaces[j];
						f.WriteBuffer(&s->MatID,1);
						f.WriteBuffer(&s->LightmapID, 1);
						f.WriteBuffer(&s->VertexCount, 1);
						f.WriteBuffer(s->Vertices, s->VertexCount);
					}
					BSP[i].LeafInfo->SaveToStream(&f);
				}
			}
			if (PVS)
				PVS->SaveBuffer(&f);
			for (int i=0; i<Entities.Count(); i++)
			{
				String(Entities[i]->GetDesc()->ClassName()).SaveToStream(&f);
				Entities[i]->Serialize(&f);
			}
			int count = Cubemaps.Count();
			f.WriteBuffer(&count, 1);
			bool valid = true;
			for (int i=0; i<count; i++)
				if (Cubemaps[i].Cubemap == 0)
				{
					valid = false;
					break;
				}
			for (int i=0; i<count; i++)
			{
				f.WriteBuffer(&Cubemaps[i].Position, 1);
			}
			f.WriteBuffer(&valid, 1);
			if (valid)
			{
				for (int i=0; i<count; i++)
				{
					Cubemaps[i].Cubemap->SaveToStream(&f);
				}
			}
		}

		void Scene::BspFillParent(int id)
		{
			for (int i=0; i<2; i++)
			{
				int c = BSP[id].Children[i];
				if (c!=0xFFFF)
				{
					BSP[c].Parent = id;
					BspFillParent(c);
				}
			}
		}

		bool Scene::IsNegativeNode(int id)
		{
			int parent = BSP[id].Parent;
			if (parent != 0xFFFF)
			{
				return (BSP[parent].Children[1] == id);
			}
			return false;
		}

		void Scene::Load(const String & fileName)
		{
			FileStream f(fileName, gxfmRead);
			SceneHeader h;
			f.ReadBuffer(&h, 1);
			if (!h.Verify())
				throw IllegalSceneHeaderException();
			Clear();
			Vertices.SetSize(h.VertexCount);
			Lightmaps.SetSize(h.LightmapCount);
			MatNames.SetSize(h.MaterialCount);
			Portals.SetSize(h.PortalCount);
			BSP.SetSize(h.BSP_NodeCount);
			f.ReadBuffer(Vertices.Buffer(), Vertices.Count());
			f.ReadBuffer(Lightmaps.Buffer(), Lightmaps.Count());
			for (int i=0; i<MatNames.Count(); i++)
				MatNames[i].LoadFromStream(&f);
			for (int i=0; i<h.PortalCount; i++)
			{
				f.ReadBuffer(&(Portals[i].Leaf1),2);
				Portals[i].Polygon = new ConvexHull::Polygon();
				f.ReadBuffer(&Portals[i].Polygon->plane, 1);
				int vc = 0;
				f.ReadBuffer(&vc, 1);
				Portals[i].Polygon->vertices.SetSize(vc);
				f.ReadBuffer(Portals[i].Polygon->vertices.Buffer(), vc);
			}
			for (int i=0; i<BSP.Count(); i++)
			{
				f.ReadBuffer(&BSP[i].ChildBits,1);
				if (!BSP[i].IsLeaf())
				{
					f.ReadBuffer(BSP[i].DividePlane,4);
				}
				else
				{
					f.ReadBuffer(&BSP[i].PVS_ID, 1);
					f.ReadBuffer(&BSP[i].SurfaceCount, 1);
					BSP[i].Surfaces = new Surface[BSP[i].SurfaceCount];
					for (int j=0; j<BSP[i].SurfaceCount; j++)
					{
						Surface *s = &BSP[i].Surfaces[j];
						f.ReadBuffer(&s->MatID,1);
						f.ReadBuffer(&s->LightmapID, 1);
						f.ReadBuffer(&s->VertexCount, 1);
						s->Vertices = new UInt[s->VertexCount];
						f.ReadBuffer(s->Vertices, s->VertexCount);
					}
					BSP[i].LeafInfo = new LeafInfo();
					BSP[i].LeafInfo->LoadFromStream(&f);
				}
				
			}
			PVS = new PotentiallyVisibleSet(h.PVS_Size);
			if (h.PVS_Size)
				PVS->LoadBuffer(&f);
			for (int i=0; i<h.EntityCount; i++)
			{
				String className;
				className.LoadFromStream(&f);
				IEntity * ent = Global->GetEntityDesc(className)->Create(&f);
				if (ent)
					Entities.Add(ent);
				else
					throw DamagedEntityException();
			}
			int count = 0;
			f.ReadBuffer(&count, 1);
			for (int i=0; i<count; i++)
			{
				CubemapProbe probe;
				f.ReadBuffer(&probe.Position, 1);
				Cubemaps.Add(probe);
			}
			bool valid = false;
			f.ReadBuffer(&valid, 1);
			if (valid)
			{
				for (int i=0; i<count; i++)
				{
					Cubemaps[i].Cubemap = new Cubemap(&f);
				}
			}
			BspFillParent(0);
		}

		Scene::Scene()
		{
		}

		Scene::~Scene()
		{	
			Clear();
		}

		void Scene::Clear()
		{
			for (int i=0; i<Entities.Count(); i++)
			{
				Entities[i]->GetDesc()->Destroy(Entities[i]);
			}
			Entities.Clear();
			for (int i=0; i<Portals.Count(); i++)
			{
				delete Portals[i].Polygon;
				Portals[i].Polygon = 0;
			}
			for (int i=0; i<BSP.Count(); i++)
				BSP[i].Destroy();
			BSP.Clear();
		}

		class Stack
		{
		public:
			int stack[64];
			int count;
			Stack()
			{
				count = 0;
			}
			void Push(int id)
			{
				stack[count] = id;
				count ++;
			}
			int Pop()
			{
				count --;
				return stack[count];
			}
			int GetTop()
			{
				return stack[count-1];
			}
			int Count()
			{
				return count;
			}
		};

		void Scene::SelectLeaf(vec3 & point, int & leafID)
		{
			leafID = TraverseBSP(this, 0, point);
		}

		void Scene::SelectLeaf(const BBox & bbox, Array<int> & leaves)
		{
			throw gxNotImplementedException();
		}

		void Scene::SelectLeaf(const vec3 & point, float rad, Array<int> & leaves)
		{
			throw gxNotImplementedException();
		}

		void Scene::SelectLeaf(const vec3 & p1, const vec3 &p2, Array<int> & leaves)
		{
			leaves.Clear();
			Stack stack;
			stack.Push(0);
			while (stack.Count())
			{
				int node = stack.Pop();
				if (BSP[node].IsLeaf())
				{
					if (!IsNegativeNode(node))
						leaves.Add(node);
				}
				else
				{
					float dist1, dist2;
					float * plane;
					plane = BSP[node].DividePlane;
					dist1 = plane[0]*p1.x+plane[1]*p1.y+plane[2]*p1.z+plane[3];
					dist2 = plane[0]*p2.x+plane[1]*p2.y+plane[2]*p2.z+plane[3];
					if (dist1*dist2 < 1.0f)
					{
						if (BSP[node].Children[0] != 0xFFFF)
							stack.Push(BSP[node].Children[0]);
						if (BSP[node].Children[1] != 0xFFFF)
							stack.Push(BSP[node].Children[1]);
					}
					else
					{
						if (dist2<dist1)
							dist1 = dist2;
						if (dist1<-0.1f)
						{
							if (BSP[node].Children[1] != 0xFFFF)
								stack.Push(BSP[node].Children[1]);
						}
						else if (dist1>0.1f)
						{
							if (BSP[node].Children[0] != 0xFFFF)
								stack.Push(BSP[node].Children[0]);
						}
						else
						{
							if (BSP[node].Children[0] != 0xFFFF)
								stack.Push(BSP[node].Children[0]);
							if (BSP[node].Children[1] != 0xFFFF)
								stack.Push(BSP[node].Children[1]);
						}
					}
				}
			}
		}

		void Scene::LineSegIntersection(const vec3 & p1, const vec3 & p2, Intersection & inter, bool getNearest)
		{
			inter.intersected = false;
			Array<int> leaves;
			leaves.SetCapacity(20);
			SelectLeaf(p1,p2,leaves);
			vec3 & dir = p2-p1;
			float len = dir.GetLength();
			for (int i=0; i<leaves.Count(); i++)
			{
				BSP_Node * node = &BSP[leaves[i]];
				for (int j=0; j<node->SurfaceCount; j++)
				{
					vec3 vinter;
					ConvexHull::Polygon * poly = node->LeafInfo->SurfacePolygons[j].operator ->();
					vec3 tp = p1;
					bool intersect = RayPlaneIntersection(tp, dir, poly->plane, vinter);
					vec3 length = vinter-tp;
					intersect = intersect && length.GetLength()<len;
					if (intersect)
					{
						for (int k=0; k<poly->EdgePlanes.Count(); k++)
						{
							float dist = poly->EdgePlanes[k].PointDistance(vinter);
							if (dist<0.0f || dist>len)
							{
								intersect = false;
								break;
							}
						}
					}
					if (intersect)
					{
						if (getNearest)
						{
							if (!inter.intersected || (vinter-p1).GetLength() < (inter.point-p1).GetLength())
							{
								inter.point = vinter;
								inter.intersected = true;
								inter.surf = &node->Surfaces[j];
							}
						}
						else
						{
							inter.point = vinter;
							inter.intersected = true;
							inter.surf = &node->Surfaces[j];
							return;
						}
					}
				}
			}

		}

		unsigned char PotentiallyVisibleSet::masks[8] = 
		{
			0x01,0x02,0x04,0x08,
			0x10,0x20,0x40,0x80
		};

		PotentiallyVisibleSet::PotentiallyVisibleSet(int nodeCount)
		{
			count = nodeCount;
			buflen = (int)(ceil(count*(count-1)/16.0f));
			buffer = new unsigned char[buflen];
			memset(buffer, 0, sizeof(unsigned char)*buflen);
		}

		PotentiallyVisibleSet::~PotentiallyVisibleSet()
		{
			delete [] buffer;
		}

		bool PotentiallyVisibleSet::GetBit(int i)
		{
			if (i>=0 && i< buflen*8)
			{
				int m = i%8;
				int idx = i/8;
				return ((buffer[idx]&masks[m])!=0);
			}
			else
				return false;
		}

		void PotentiallyVisibleSet::SetBit(int i, bool val)
		{
			if (i>=0 && i< buflen*8)
			{
				int m = i%8;
				int idx = i/8;
				if (val)
					buffer[idx] = buffer[idx]|masks[m];
				else
					buffer[idx] = buffer[idx]&(~masks[m]);
			}
		}

		bool PotentiallyVisibleSet::Get(int i, int j)
		{
			if (i==j)
				return true;
			if (i>j)
			{
				int t = i;
				i = j;
				j = t;
			}
			int idx = (j-1)*j/2+i;
			return GetBit(idx);
		}

		void PotentiallyVisibleSet::Set(int i, int j, bool val)
		{
			if (i==j)
				return;
			if (i>j)
			{
				int t = i;
				i = j;
				j = t;
			}
			int idx = (j-1)*j/2+i;
			return SetBit(idx, val);
		}

		void PotentiallyVisibleSet::SaveBuffer(Stream * s)
		{
			s->WriteBuffer(buffer, buflen);
		}

		void PotentiallyVisibleSet::LoadBuffer(Stream * s)
		{
			s->ReadBuffer(buffer, buflen);
		}

		int PotentiallyVisibleSet::GetSize()
		{
			return count;
		}

		void PotentiallyVisibleSet::Clear(unsigned char val)
		{
			memset(buffer, val, sizeof(unsigned char)*buflen);
		}
	}
}